package 滑动窗口;

public class 最小覆盖子串 {


    public static String minWindow2(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int kinds = 0;
        for (char x : t) {
            if (hash2[x]++ == 0) {
                kinds++;
            }
        }

            int min = Integer.MAX_VALUE, begin = -1, size = t.length;
            for (int left = 0, right = 0, count = 0; right < s.length; right++) {
                char in = s[right];
                if (++hash1[in] == hash2[in]) count++;

                while (count == kinds) {
                    if (right - left + 1 < min) {
                        begin = left;
                        min = right - left + 1;
                    }
                    char out = s[left++];
                    if (hash1[out]-- == hash2[out]) {
                        count--;
                    }
                }
            }
            if (begin == -1) return new String();

            else return ss.substring(begin, begin + min);

    }
        public static void main (String[]args){
            String ss = "aa";
            String tt = "aa";
            String a = minWindow2(ss, tt);
            System.out.println(a);
        }


}
